<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>排序 | ZHB&#39;s Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="数据结构课后整理的一部分内容。（没啥干货，就不要再点开看了）">
<meta name="keywords" content="Data Structure">
<meta property="og:type" content="article">
<meta property="og:title" content="排序">
<meta property="og:url" content="https://gkzhb.github.io/2018/11/sort/index.html">
<meta property="og:site_name" content="ZHB&#39;s Blog">
<meta property="og:description" content="数据结构课后整理的一部分内容。（没啥干货，就不要再点开看了）">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2019-01-31T07:38:44.121Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="排序">
<meta name="twitter:description" content="数据结构课后整理的一部分内容。（没啥干货，就不要再点开看了）">
  
    <link rel="alternate" href="/atom.xml" title="ZHB&#39;s Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link rel="stylesheet" href="/css/sourcecodepro.css">
    <!-- <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css"> -->
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">ZHB&#39;s Blog</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="https://gkzhb.github.io"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-sort" class="article article-type-post" itemscope itemprop="blogPost">



  <div class="article-meta">
    <a href="/2018/11/sort/" class="article-date">
  <time datetime="2018-11-05T15:15:59.000Z" itemprop="datePublished">2018-11-05</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/categories/Programming/">Programming</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      排序
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
		<!-- Table of Contents -->
		
			<div id="toc" class="toc-article">
				<strong class="toc-title">Table of Content</strong>
				<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#排序-sorting-的定义"><span class="toc-number">1.</span> <span class="toc-text">排序 (sorting) 的定义</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#排序的稳定性"><span class="toc-number">2.</span> <span class="toc-text">排序的稳定性</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#排序的分类"><span class="toc-number">3.</span> <span class="toc-text">排序的分类</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#内存使用"><span class="toc-number">3.1.</span> <span class="toc-text">内存使用</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#排序实现手段"><span class="toc-number">3.2.</span> <span class="toc-text">排序实现手段</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#实现难易"><span class="toc-number">3.3.</span> <span class="toc-text">实现难易</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#排序方法介绍"><span class="toc-number">4.</span> <span class="toc-text">排序方法介绍</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#基本排序方法"><span class="toc-number">4.1.</span> <span class="toc-text">基本排序方法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#冒泡排序"><span class="toc-number">4.1.1.</span> <span class="toc-text">冒泡排序</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#插入排序"><span class="toc-number">4.1.2.</span> <span class="toc-text">插入排序</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#高级排序"><span class="toc-number">4.2.</span> <span class="toc-text">高级排序</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#快速排序"><span class="toc-number">4.2.1.</span> <span class="toc-text">快速排序</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#归并排序"><span class="toc-number">4.2.2.</span> <span class="toc-text">归并排序</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#性质"><span class="toc-number">4.2.2.1.</span> <span class="toc-text">性质</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#内容"><span class="toc-number">4.2.2.2.</span> <span class="toc-text">内容</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#堆排序"><span class="toc-number">4.2.3.</span> <span class="toc-text">堆排序</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#计数排序"><span class="toc-number">4.2.4.</span> <span class="toc-text">计数排序</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#性质-1"><span class="toc-number">4.2.4.1.</span> <span class="toc-text">性质</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#内容-1"><span class="toc-number">4.2.4.2.</span> <span class="toc-text">内容</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#桶排序"><span class="toc-number">4.2.5.</span> <span class="toc-text">桶排序</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#基数排序"><span class="toc-number">4.2.6.</span> <span class="toc-text">基数排序</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#参考资料"><span class="toc-number">5.</span> <span class="toc-text">参考资料</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#推荐视频"><span class="toc-number">5.1.</span> <span class="toc-text">推荐视频</span></a></li></ol></li></ol>
			</div>
		
        <p>数据结构课后整理的一部分内容。（没啥干货，就不要再点开看了）</p>
<a id="more"></a>
<h2 id="排序-sorting-的定义">排序 (sorting) 的定义</h2>
<p>排序: 将一个数据元素（或记录）的任意序列重新排列成一个按关键字 <strong>有序</strong> 的序列。</p>
<ul>
<li>升序：关键字从小到大</li>
<li>降序：关键字从大到小</li>
</ul>
<h2 id="排序的稳定性">排序的稳定性</h2>
<p>若序列中关键字值相等的节点经过某种排列方法进行排序之后，仍能保持它们在排序前的相对顺序，则称这种排序方法是 <strong>稳定</strong> 的；否则，称这种排序方法是 <strong>不稳定</strong> 的。</p>
<p>用符号表达： 在序列 <span class="math inline">\(a_0\)</span>, <span class="math inline">\(a_1\)</span>, <span class="math inline">\(a_2\)</span>, ... , <span class="math inline">\(a_{n-1}\)</span> 排序前 ( <span class="math inline">\(a_i\)</span> 对应关键字为 <span class="math inline">\(k_i\)</span>) ，若 i &lt; j ^ <span class="math inline">\(k_i\)</span> = <span class="math inline">\(k_j\)</span>，且排序后，<span class="math inline">\(a_i\)</span> 一定仍在 <span class="math inline">\(a_j\)</span> 之前，则称这种排序方法是稳定的，否则这种排序方法是不稳定的。</p>
<h2 id="排序的分类">排序的分类</h2>
<h3 id="内存使用">内存使用</h3>
<ul>
<li><p>内部排序 排序期间全部节点都存储于内存，并在内存中调整等待排序节点的存放位置。</p></li>
<li><p>外部排序 排序期间大部分节点存储于外存中，排序过程中借助内存，调整那些存放在外存，等待排序的节点的存放值。</p></li>
</ul>
<h3 id="排序实现手段">排序实现手段</h3>
<ul>
<li><p>基于“比较-交换”的排序 如 插入排序、冒泡排序、快速排序、希尔排序、堆排序等。</p></li>
<li><p>基于“分配”的排序 如 基数排序、桶排序等。</p></li>
</ul>
<h3 id="实现难易">实现难易</h3>
<ul>
<li><p>基本排序方法 通常认为包括插入排序、冒泡排序、选择排序。</p></li>
<li><p>高级排序方法 如 快速排序、归并排序、堆排序等。</p></li>
</ul>
<h2 id="排序方法介绍">排序方法介绍</h2>
<h3 id="基本排序方法">基本排序方法</h3>
<h4 id="冒泡排序">冒泡排序</h4>
<h4 id="插入排序">插入排序</h4>
<h3 id="高级排序">高级排序</h3>
<h4 id="快速排序">快速排序</h4>
<h4 id="归并排序">归并排序</h4>
<h5 id="性质">性质</h5>
<ul>
<li>稳定性</li>
</ul>
<h5 id="内容">内容</h5>
<p>归并排序可分为 自下而上 和 自上而下 两种方式（本质相同） 先将数组拆分成许多很小的数组分别进行排序，然后小数组两两合并成较大的有序数组，较大的有序数组继续两两合并，重复该过程直至完全合并。</p>
<h4 id="堆排序">堆排序</h4>
<ol type="1">
<li>构造出 <code>堆</code> 这种数据结构（可以用数组存储）</li>
<li>得到所有数据中的最大/小值（位于堆的根节点上）</li>
<li>将其与堆中末尾元素互换，堆元素数目减一</li>
<li>调整堆，得到剩下的最值，重复操作</li>
</ol>
<h4 id="计数排序">计数排序</h4>
<h5 id="性质-1">性质</h5>
<ul>
<li>稳定性</li>
</ul>
<h5 id="内容-1">内容</h5>
<p>创建一个和数据范围一样大的数组来存储每个数据出现次数</p>
<h4 id="桶排序">桶排序</h4>
<p>通过将所有数据根据大小均匀分配在 n 个桶中，然后对桶内的元素排序</p>
<ol type="1">
<li>找出数组最值，确定桶的数目</li>
<li>计算桶的大小，由此可得到每个桶存储数据的范围</li>
<li>将待排序数据放入对应桶中</li>
<li>在桶内部进行排序，并将所有桶合并以完成排序</li>
</ol>
<h4 id="基数排序">基数排序</h4>
<p>基数排序分为 LSD(最低位优先法) 和 MSD(最高位优先法) 两种 中文 ##### LSD</p>
<ol type="1">
<li>根据进制数 n 设置 n 元数组 count，count[i] 统计第 j 位数字为 i 的数的数目</li>
<li>将 count 从前到后累加，即 <code>count[i] = count[i] + count[i - 1]</code>(i 从 1 到 n - 1) ，得到 count[i] 即为 count[i] 所统计数字组在原数组中的结束位置</li>
<li>根据 count 数组 <strong>从后向前</strong> 遍历原排序数组将每个数字放入数组中对应位置(第 j 位数字 i 对应的 count[i] - 1 即为对应位置)，同时更新 count 数组(count[i] 递减)</li>
<li>j 从最低位循环到最高位，即可完成排序</li>
</ol>
<h2 id="参考资料">参考资料</h2>
<ul>
<li><a href="https://blog.csdn.net/sunjinshengli/article/details/70738527" target="_blank" rel="noopener"><strong>排序算法（三）：计数排序与桶排序</strong></a> &lt;- 这个靠谱</li>
<li><a href="https://blog.csdn.net/YinhJiang/article/details/80397415" target="_blank" rel="noopener">经典排序思想——桶排序</a></li>
<li><a href="https://blog.csdn.net/jp413670706/article/details/52745767" target="_blank" rel="noopener">基数排序与计数排序</a></li>
<li><a href="https://blog.csdn.net/msdnwolaile/article/details/52459452" target="_blank" rel="noopener">计数排序和基数排序和桶排序</a> &lt;- <a href="http://www.cnblogs.com/kkun/archive/2011/11/23/2260299.html" target="_blank" rel="noopener">经典排序算法 - 计数排序Counting sort</a></li>
</ul>
<h3 id="推荐视频">推荐视频</h3>
<ul>
<li><a href="https://www.bilibili.com/video/av685670?from=search&amp;seid=13221889579576927281" target="_blank" rel="noopener">6 分钟演示 15 种排序算法 - Bilibili</a></li>
</ul>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://gkzhb.github.io/2018/11/sort/" data-id="cjx8qks8t000inrw8trbextkm" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Data-Structure/">Data Structure</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2018/11/grep/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          Using Grep &amp; Regular Expressions
        
      </div>
    </a>
  
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/Landscape/">Landscape</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Linux/">Linux</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Programming/">Programming</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Self-hosting/">Self-hosting</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/Software/">Software</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Anki/">Anki</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Blog/">Blog</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Command-Line/">Command Line</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Data-Structure/">Data Structure</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Games/">Games</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Hometown/">Hometown</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Linux/">Linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Network/">Network</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Read-It-Later/">Read-It-Later</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Recall/">Recall</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Regular-Expression/">Regular Expression</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Server/">Server</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Spring/">Spring</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/折腾/">折腾</a></li></ul>
    </div>
  </div>


  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 Haibin Zhang<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<!-- <script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script> -->

<!-- <script src="http://apps.bdimg.com/libs/jquery/2.0.3/jquery.min.js"></script> -->
<script src="/mathjax/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<script src="/js/jquery.min.js"></script>

  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>




  </div>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
		messageStyle: "none",
		showProcessingMessages: false,
        tex2jax: {
            inlineMath: [ ["$","$"], ["\\(","\\)"] ],
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code'],
            processEscapes: true
        }
    });
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax();
        for (var i = 0; i < all.length; ++i)
            all[i].SourceElement().parentNode.className += ' has-jax';
    });
</script>
<!-- <script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> -->
<script src="/mathjax/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

</body>
</html>